using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0110. 平衡二叉树")]
    public class No0110_IsBalanced : AbsBaseTestItem
    {
        /*
        给定一个二叉树，判断它是否是高度平衡的二叉树。
        本题中，一棵高度平衡二叉树定义为：
            一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
        */

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        public override void OnTest()
        {
            Assert.TestExe(IsBalanced,
                new TreeNode(3)
                {
                    left = new TreeNode(9),
                    right = new TreeNode(20)
                    {
                        left = new TreeNode(15),
                        right = new TreeNode(7),
                    },
                }, true);
            Assert.TestExe(IsBalanced,
                new TreeNode(1)
                {
                    left = new TreeNode(2)
                    {
                        left = new TreeNode(3)
                        {
                            left = new TreeNode(4),
                            right = new TreeNode(4),
                        },
                        right = new TreeNode(3),
                    },
                    right = new TreeNode(2),
                }, false);
        }

        public bool IsBalanced(TreeNode root)
        {
            int calcHeight(TreeNode node)
            {
                if (node == null) return 0;
                int left_h = calcHeight(node.left);
                int right_h = calcHeight(node.right);
                if (left_h == -1 || right_h == -1 || Math.Abs(left_h - right_h) > 1)
                {
                    return -1;
                }
                return Math.Max(left_h, right_h) + 1;
            }
            return calcHeight(root) >= 0;
        }
    }
}
